МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ
КОДЕРІВ І ДЕКОДЕРІВ КОДІВ ХЕМІНГА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 1
з курсу “Основи збору, передачі та обробки інформації”
для студентів базового напряму 6.1601
“Інформаційна безпека”
Затверджено
на засiданнi кафедри
"Захист інформації"
протокол № 21 вiд 14. 06. 2007 p.
Львів 2007
Дослідження кодоутворення та принципів побудови кодерів і декодерів кодів Хемінга: Методичні вказівки до лабораторної роботи № 1 з курсу «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Інформаційна безпека» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, Я. Р. Совин. – Львів: НУЛП, 2007. – 14 с.
Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., Я. Р. Совин, канд. техн. наук, асист.
Відповідальний за випуск В. В. Хома, док. техн. наук, проф.
Рецензенти: А. Е. Лагун, канд. техн. наук, доц., З. М. Стрілецький, канд. техн. наук, доц.
мета роботи – вивчити принципи побудови кодів Хемінга та одержати практичні навики розробки функціональ них схем кодерів і декодерів.
ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Простота реалізації та ефективне забезпечення завадостійкості зумовили широке застосування коду Хемінга (КХ) не лише у телемеханіці, але і в обчислювальній техніці та зв’язку. Відомі декілька різновидностей КХ, які характеризуються різною коректуючою здатністю [1, 2]. Код Хемінга з d = 3 забезпечує виявлення двократних (r = 2) або виправлення однократної (S = 1) помилки, оскільки d = r + 1 або d = 2S + 1.
Вихідним для коду Хемінга є первинний (двійковий або двійково-десятковий) -розрядний код, до якого в результаті вторин ного кодування додають контрольних розрядів. Отже, загальна довжина кодової комбінації (КК) збільшиться до .
Кількість робочих комбінацій. Число контрольних роз рядів знаходять із виразу [2, 3]:
(1)
В табл. 1 наведені значення п і , для різних , що задовольняють умову (1).
Таблиця 1
3
4
5
6
7
8
п
7
15
31
63
127
255
4
11
26
57
120
247
Оскільки при збільшенні кількості інформаційних розрядів , кількість контрольних розрядів зростає незначно, надлишковість коду,
(2)
зменшується, а швидкість передачі інформації
(3)
зростає.
Побудова коду Хемінга, що виправляє всі одиничні помилки (d = 3) здійснюється так. Спочатку визначають необхідну кіль кість контрольних розрядів на підставі співвідношення (1). Далі визначають їх розташування в кодовій комбінації. Для спрощення кодування і декодування контрольні символи розташовують на місцях КК, кратних степеню 2, тобто на позиціях 1, 2, 4, 8, 16 і т.д., хоча їх розташування може бути довільним. Інформаційні розряди розташовуються на вільних місцях. На основі зазначеного для 15-розрядної кодової комбінації можна записати:
де І3 перший (молодший), а І15 одинадцятий (старший) розряд робочої (інформаційної) КК.
У циклічному коді Хемінга контрольні символи розташову ються після інформаційних розрядів [4].
Потім знаходять значення контрольних символів (0 або 1) підсумовуючи за модулем два (перевірка на парність) значення певних інформаційних розрядів за алгоритмом Хемінга так:
. (4)
; (5)
; (6)
; (7)
Щоб виключити необхідність багатократного використання цих рівнянь для визначення контрольних символів, для кожної із робочих КК застосовують так звану утворюючу матрицю. Утворююча матриця коду Хемінга (n, ni) складаєтьс...
